package codetop.microsoft.T912;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-06 22:18:06 星期二
 */
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right)
            return;
        int base = nums[left], i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= base)
                --j;
            while (i < j && nums[i] <= base)
                ++i;
            if (i < j)
                swap(nums, i, j);
            else
                swap(nums, left, j);
        }
        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right);
    }

    private void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}
